package backtracking;
/**
 * 
 * @author victor
 * 
 */
public class MochilaBacktracking {
	
	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int[] L = new int[] { 1, 2, 3, 5, 6, 7, 9 };
		sumaSubconjuntos(L, 13);
	}

	/**
	 * 
	 * @param L
	 * @param s
	 */
	private static void sumaSubconjuntos(int[] L, int s) {
		buscarSubconjs(L.length, 0, 0, L, s, new boolean[L.length]);
	}

	/**
	 * 
	 * @param L
	 * @param v
	 */
	private static void imprimir(int[] L, boolean[] v) {
		for (int i = 0; i < v.length; i++)
			if (v[i])
				System.out.print(L[i] + " ");
		System.out.println();
	}

	/**
	 * 
	 * @param n
	 * @param i
	 * @param p
	 * @param L
	 * @param s
	 * @param subconj
	 */
	private static void buscarSubconjs(int n, int i, int p, int[] L, int s, boolean[] subconj) {
		for (int k = 0; k <= 1; k++) {
			int nuevoP = p + k * L[i];
			if (nuevoP <= s) {
				if (k == 0)
					subconj[i] = false;
				else
					subconj[i] = true;

				if (i == n - 1) {
					if (nuevoP == s)
						imprimir(L, subconj);
				} else
					buscarSubconjs(n, i + 1, nuevoP, L, s, subconj);
			}
			// nuevoP = p - k*L[i]; lo suprimimos por innecesario
		}
	}

}
